package com.ronz.sort;

import java.util.Arrays;

/**
 * @Description 归并排序
 * @Author Ronz
 * @Date 2021/1/11 16:24
 * @Version 1.0
 */
public class No6_MergeSort {

    static int x=0;

    public static void main(String[] args) {
        int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
        int temp[] = new int[arr.length];
        mergeSort(arr,temp,0,arr.length-1);
    }



    /**
     * 归并排序
     * @param arr   待归并排序序列
     * @param temp  临时存储合并后的序列
     * @param left  左子序列的起点
     * @param last  右子序列的终点
     * @return void
     */
    public static void mergeSort(int[] arr, int[]temp, int left, int last) {
        if(left < last) {
            int mid = (left + last) / 2;       //中间索引
            mergeSort(arr,temp, left, mid);
            mergeSort(arr, temp,mid + 1, last );
            merge(arr, temp, left, mid, last);
        }
    }

    /**
     * 合并两个有序序列
     * @param arr   两个子序列组成的原始数组，arr[left]~arr[mid] 为左子序列、arr[mid+1]~arr[last] 为右子序列
     * @param temp  临时存储归并后的序列
     * @param left  指向左子序列的首个元素
     * @param mid   指向左子序列的末尾元素
     * @param last  指向待归并序列的最后一个元素
     * @return void
     */
    public static void merge(int[] arr, int[] temp, int left, int mid, int last){
        int i = left, j = mid + 1;  // i 为左子序列起点，j 为右子序列起点
        int m = mid, n = last;      // m 为左子序列终点，n 为右子序列终点
        int t = 0;                  // 临时数组索引

        /*
            把两个子序列组成的数组元素按照规则放入到 temp 数组中，
            直到有一个子序列的元素被读完。
        */
        while(i<=m && j<=n) {
            if (arr[j] <= arr[i]) {
                temp[t] = arr[j];
                t += 1;
                j += 1;
            } else {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            }
        }
        /* 哪个子序列元素有剩余，就都读取到 temp 中 */
        while(i<=mid){  // 如果是左子序列还有剩余元素
            /* 把剩余元素都填充到 temp */
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }
        while(j<=last){    // 如果是右边的序列元素有剩余
            /* 把剩余元素都填充到 temp */
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }

        /* 从 temp 数组中 copy 数据到原数组 */
        for (i=0; i<t; i++){
            arr[left + i] = temp[i];
        }

        // 将 temp 数组的元素拷贝到 arr 对应位置
        System.out.println("第" + ++x + "次合并后：" + Arrays.toString(temp));
    }

}
